Digital filters are often important components of audio and video processing systems. One type of digital filter often used in such systems is a finite impulse response (FIR) filter. A typical FIR filter is a linear-phase filter that delays the input signal without distorting the phase of the input signal. The delay on the input signal may be implemented as a set of memory elements, i.e., a delay line, that store the delayed elements of the FIR calculation.
In general, a FIR filter operates by convolving the input signal with the impulse response, i.e., the set of coefficients, of the filter. In implementation, different techniques may be used to perform the convolution such as, for example, direct time domain convolution, single-block convolution, multi-block convolution, and frequency-domain delay line (FDL) convolution. While there is no inherent latency in direct time domain convolution, the computational cost may be high for long convolutions as the computation cost increases linearly with the length of the filter. Thus, direct time domain convolution may be unsuitable for real-time filtering.
Single-block convolution, also referred to as frequency domain block convolution, is based on the fact that multiplication in the frequency domain is equivalent to circular convolution in the time domain. Since this technique uses circular convolution, a Discrete Fourier Transform (DFT) is used. The DFT may be implemented with a Fast Fourier Transform (FFT) algorithm. Two well-known techniques for single block convolution are referred to as “overlap-save” and “overlap-add.” Each of these techniques computes the DFT of the input sample block, multiplies the result by the DFT of the entire impulse response, and obtains a time-domain output block of samples by performing the inverse transform of the result of the multiplication. The DFT of the impulse response may be pre-computed. The computational cost of these techniques increase logarithmically with the length of the filter, rather than linearly. However, these techniques have an inherent input to output latency equal to the length of the block as the input sample block must be full before beginning computation. Thus, single-block convolution may also be unsuitable for real-time filtering due to the high latency.
Multi-block convolution may be used to reduce the latency while keeping the computational cost at an acceptable level. In multi-block convolution, the filter is divided into shorter blocks, frequency-domain block convolutions are performed on the shorter blocks, and the outputs of the convolutions are summed to obtain the filtered result. The length of the filter blocks may be chosen according to different criteria, such as a desired latency.
In FDL convolution, similar to multi-block convolution, the filter is divided into shorter blocks, and a DFT of each block is calculated using an FFT algorithm. A DFT of the input sample block is also performed using an FFT algorithm, the DFT of the input sample block is spectrally multiplied with the DFTs of each of the filter blocks, and the blocks resulting from the spectral multiplications are overlap-added to generate an output spectral block, and an inverse FFT is performed on the output spectral block to create a time domain output block. The length of the filter blocks maybe chosen, for example, to minimize the computational cost of FDL convolution. FDL convolution is describe in more detail in U.S. Pat. No. 6,625,629, entitled “System and Method for Signal Processing Using an Improved Convolution Technique,” filed on May 23, 2000.
While digital FIR filters using known convolution techniques may be adequate for many audio and video applications, there is an ever present demand for faster and more complex digital signal processing in such applications. Accordingly, improvements in digital FIR filters are needed.